package com.zj.leetcode.medium.greed;

import java.util.Stack;

/**
 * @program: algorithm
 * @description: 去除重复字母
 * 316 remove-duplicate-letters
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class RemoveDuplicateLetters {
    public static void main(String[] args) {
        Solution solution = new RemoveDuplicateLetters().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String removeDuplicateLetters(String s) {
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < s.length(); i++) {
                Character c = s.charAt(i);
                if (stack.contains(c)) {
                    continue;
                }
                while (!stack.isEmpty() && stack.peek() > c && s.indexOf(stack.peek(), i) != -1) {
                    stack.pop();
                }
                stack.push(c);
            }
            char chars[] = new char[stack.size()];
            for (int i = 0; i < stack.size(); i++) {
                chars[i] = stack.get(i);
            }
            return new String(chars);

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
